Data clustering is the process of partitioning a set of data objects into meaning clusters or groups. Due to the vast usage of clustering Algorithms in many fields, a lot of research is still going on to find the best and efficient clustering Algorithm to partition the data items. K-means is simple and easy to implement, but it suffers from initialization of cluster center and hence trapped in local optimum. In this paper, a new hybrid data clustering approach which combines the modified Krill Herd and K-means Algorithms, named as K-MKH, is proposed. K-MKH Algorithm utilizes the power of quick convergence behaviour of K-means and efficient global exploration of Krill Herd and random phenomenon of Levy flight method. The Krill-Herd Algorithm is modified by incorporating Levy flight into it to improve the global exploration. The proposed Algorithm is tested on artificial and real life datasets. The simulation results are compared with other methods such as K-means, Particle Swarm Optimization (PSO), Original Krill Herd (KH), hybrid K-means and KH. Also the proposed Algorithm is compared with other evolutionary Algorithms such as hybrid modified cohort intelligence and K-means (K-MCI), Simulated Annealing (SA), Ant Colony Optimization (ACO), Genetic Algorithm (GA), Tabu Search (TS), Honey Bee Mating Optimization (HBMO) and K-means++. The comparison shows that the proposed Algorithm improves the clustering results and has high convergence speed.